Let's start with the easiest automata model over picture languages. The finite
automata which is also called four-way finite automata will be abbreviated
as 4FA in this paper. The 4FA was introduced in 1967 by M. Blum and C. Hewitt
(see~\cite{blum1967automata}) and can also be found
in~\cite{morita2004twodimensional},~\cite{giammarresi1997twodimensional},~\cite{inoue1979unacceptable},~\cite{ito1997nonclosure}.
This type of automaton reads one pixel of the input picture. According to the
current state, the automaton moves to one of the neighboring pixels. Afterwards
the automaton changes its state.
Formally, a non-deterministic 4FA can be defined as follows.
\begin{definition}
A \emph{non-deterministic two-dimensional finite automaton} abbreviated as 4NFA
is a 6-tuple $M = (Q, \Sigma, \delta, q_0, q_a, q_r)$, where
\begin{compactitem}
	\item $Q$ is a finite set of states,
	\item $\Sigma$ is a finite set of input symbols,
	\item $q_0$, $q_a$ and $q_r$ is the starting, accepting and rejecting state,
	\item $\delta: (Q \backslash \{q_a, q_r\}) \times (\Sigma \cup \{\#\})
	\rightarrow 2^{Q \times \Delta}$ is the control function, where $\# \not\in
	\Sigma$ is the boundary symbol and $\Delta = \{L, R, U, D\}$ is a set of
	directions (left, right, up and down).
\end{compactitem}
\end{definition}
A 4NFA $M$ starts at position $(1, 1)$ of an input picture $p$ and
uses transition steps for moving over $p$. It does not have to move over every
pixel and can visit each pixel at a random number of times. $M$ accepts an
input picture if it reaches the accepting state and rejects the picture, if $M$
reaches the rejecting state.

We now regard an example of a 4NFA. The 4NFA that will be presented next
accepts the language $S_{1}$ of all quadratic pictures over $\Sigma$ with odd
side length and 1 in its center. Formally, \begin{align*} 
S_{1} = \{p \mid &p \in \Sigma^{*,*}, l_1(p) = l_2(p), l_1(p) \text{ mod } 2 = 1
\wedge \\
  &p(\lfloor l_1(p) / 2 \rfloor + 1, \lfloor l_2(p) / 2 \rfloor + 1) = 1\}. 
\end{align*}
For example the 4NFA can be build as follows. For a better visualization, we
illustrate the transition function $\delta$ in form of a table, where for
example $\delta(q_0, 0) = (q_1, R)$
\begin{example}
$M = (\{q_0, \ldots, q_9, q_r, q_a\}, \{0, 1\}, \delta, q_0, q_a, q_r)$ 
\begin{center}
\begin{tabular}{c|c|c|c}
$\delta$ & 0          & 1                        & \#         \tabularnewline
\hline
$q_0$    & $(q_1, R)$ & $(q_1, R)$               & $(q_r, U)$ \tabularnewline
\hline
$q_1$    & $(q_0, D)$ & $(q_0, D)$               & $(q_2, L)$ \tabularnewline
\hline
$q_2$    & $(q_3, D)$ & $(q_3, D)$               & -          \tabularnewline
\hline
$q_3$    & $(q_r, U)$ & $(q_r, U)$               & $(q_4, U)$ \tabularnewline
\hline
$q_4$    & $(q_5, U)$ & $(q_5, U), (q_6, R)$     & $(q_r, R)$ \tabularnewline
\hline
$q_5$    & $(q_4, L)$ & $(q_4, L)$               & $(q_r, D)$ \tabularnewline
\hline
$q_6$    & $(q_7, U)$ & $(q_7, U)$               & $(q_8, L)$ \tabularnewline
\hline
$q_7$    & $(q_6, R)$ & $(q_6, R)$               & $(q_r, D)$ \tabularnewline
\hline
$q_8$    & $(q_9, U)$ & $(q_9, U)$               & -          \tabularnewline
\hline
$q_9$    & $(q_r, D)$ & $(q_r, D)$               & $(q_a, D)$ \tabularnewline
\end{tabular}
\end{center}
\label{example_finite_automata}
\end{example}
$M$ can be divided into three phases. In the first phase $M$ checks the
size of the picture. For checking the size $M$ walks along the first main
diagonal. If it reaches the symbol for the border in the state $q_1$ it
checks the pixel on the lower left position. If this pixel is also the
symbol for the border, the input picture has a quadratic size. Now $M$ changes
to phase two, starting at state $q_4$.

In the second phase, $M$ scans the first main diagonal backwards and at one
point where it reads the symbol 1 $M$ changes to phase three. Please note that
the state $q_4$ has two possible transitions. This is the reason why $M$ is a
non-deterministic 4FA.

In the third phase, starting at state $q_6$, $M$ moves his head on the second
main diagonal backwards and checks whether the point where $M$ changes to phase
three was the point in the center of the picture. Therefore, it performs the
similar transitions as in phase one. If $M$ reads the symbol of the border in
state $q_9$, $M$ has reached the upper left corner of the input picture. Now it
is ensured that the size of the quadratic picture is odd i.e. $m = 2n + 1$.
Furthermore, the symbol 1, which caused $M$ to change to phase three, must be
in the center of the input picture. So $M$ accepts the input picture. It follows
$L(M) = S_{1}$. The three phases are depicted below.
\begin{center}
\begin{tabular}{>{\centering\arraybackslash}
m{0.35cm}>{\centering\arraybackslash} m{3cm}>{\centering\arraybackslash}
m{4cm}>{\centering\arraybackslash} m{4cm}}
 & $m$ &  &  \tabularnewline 
$m$ & 
\includegraphics[width = 3cm]{img/example_finite_state_automaton1.png} &
\includegraphics[width = 3cm]{img/example_finite_state_automaton2.png} & 
\includegraphics[width = 3cm]{img/example_finite_state_automaton3.png} \tabularnewline 
\multicolumn{2}{c}{(a) The first phase.} & (b) The second phase. & (c) The third phase.
\end{tabular}
\end{center}
After we know how the 4FA works we can talk about its closure properties and
language family dependencies. At first, we want to look at the closure
properties. 
\begin{theorem}
The two classes $\familyOf{4DFA}$ and $\familyOf{4NFA}$ are closed under
intersection and union. Moreover $\familyOf{4DFA}$ is closed under complement.
\end{theorem} 
This theorem is proved by  K. Inoue, I. Takanami in~\cite{inoue1991survey}. The
next theorem is proved by K. Inoue, I. Takanami and A. Nakamura
in~\cite{inoue1978note},~\cite{inoue1980nonclosure}
and~\cite{inoue1978tapebounded}.
\begin{theorem}
$\familyOf{4DFA}$ and $\familyOf{4NFA}$ are not closed under vertical
and horizontal concatenation, vertical and horizontal closure, row and column
cyclic closure and projection.
\end{theorem}
We do not know whether the class $\familyOf{4NFA}$ is closed under complement
or not. In~\cite{kari2001newresults} J. Kari and C. Moore showed that it
is possible to say something about the closure under complement if the alphabet
only contains one symbol.
\begin{theorem}
Over unary alphabets $\familyOf{4NFA}$ is not closed under complement.
\end{theorem}
\begin{proof}
In the proof of this theorem it was shown that the language $S = \{p \in \Sigma
\mid \Sigma \text{ is unary alphabet and } l_1(p) = i \cdot l_2(p) + j \text{
for some } 0 \leq j \leq i\}$ is in $\familyOf{4NFA}$ whereas its complement is not an
element of $\familyOf{4NFA}$, which implies the theorem.
\end{proof}
In contrast to the one-dimensional case, the classes of determinstic finite
automata and of non-deterministic finite automata are not the same. Proved by M.
Blum and C. Hewitt in~\cite{blum1967automata} the following
theorem holds.
\begin{theorem} 
$\familyOf{4DFA} \subset \familyOf{4NFA}$
\end{theorem}
In this proof it was shown that for the language $S_{1}$ described in the
Example \ref{example_finite_automata} $L \in \familyOf{4NFA}$ and
$L \not\in \familyOf{4DFA}$ holds.

\begin{theorem}
	$\familyOf{RML} \subset \familyOf{4DFA}$
\end{theorem}

This has been shown in \cite{giammarresi1997twodimensional} and is the only connection between matrix grammars and automaton. 
